МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра САПР
Лабораторна робота №1
РОБОТА ЗІ СТЕКОМ
з курсу: “Алгоритми и структури данних”
Виконав студент
групи КН – 24
Прийняв
ЛЬВІВ 2008
Мета роботи:Ознайомитися iз способом подання даних в оперативнiй пам'ятi ЕОМ у виглядi лiнiйних зв'язаних спискiв та стеків.
Теоретичні відомості
Необхiдно рацiонально використовувати системнi ресурси, у першу чергу пам’ять. Для правильного застосування пам’ятi важливо розумiти способи подання у нiй даних i методи роботи з ними. У лабораторнiй роботi розглядаються структури даних у виглядi лiнiйних спискiв.
Лiнiйний список - це множина, яка складається з n>=0 вузлiв X[1], X[2],, X[n], для якої якщо n>0, то X[1] є першим вузлом; якщо 1<k<n, то k-му вузлу X[k] передує X[k-1] i за ним йде X[k+1]; X[n] є останнiм вузлом.
Операцiї, якi можна виконувати з лiнiйним списком:
отримати доступ до k-го вузла списку, щоб проаналiзувати i/або змiнити його вмiст;
ввести новий вузол безпосередньо перед k-м вузлом;
3) видалити k-вузол;
4) об'єднати кiлька лiнiйних спискiв в один;
5) зробити копiю лiнiйного списку;
6) видалити вузол iз списку;
7) знайти вузол iз заданим значенням у деякому полi.
Iснують два методи зберiгання структур даних у пам’ятi комп’ютера. Перший метод розподiлу, який використовує переваги одновимiрної властивостi пам’ятi, називається послiдовним розподiлом. Другий метод розподiлу, що базується на зберiганнi адреси чи розташування кожного елемента списку, вiдомий пiд назвою зв’язаного розподiлу.
Перший метод не використовується, якщо:
1. Вимоги до пам’ятi є непередбачуваними.
2. Даними, що зберiгаються у пам’ятi, iнтенсивно манiпулюють.
Порiвняємо два методи розподiлу пам’ятi на прикладах операцiй, що часто виконуються.
Вставлення (видалення)
1-й: щоб вставити елемент за iншим, необхiдно посунути n-2 елемента. Для великих спискiв така операцiя надто дорога. Те саме стосується і видалення.
2-й: для зв’язаного списку ця операцiя полягає у змiнi лише двох зв’язкiв.
Пошук
1-й: розраховується позицiя елемента i здiйснюється безпосереднє звертання до нього.
2-й: слід пройти всi вузли вiд першого до шуканого.
З’єднання двох списків
1-й: переносити елементи.двох
2-й: змiнити вказiвники.
Зрозумiло, що вказiвники вимагають додаткової пам’ятi. Проте вона є незначною - принаймнi пiвслова пам’ятi.
Використання зв’язаного розподiлу, як правило, передбачає iснування деякого механiзму пошуку вiльного простору для нового вузла, коли ми хочемо ввести у список деяку нову iнформацiю. Для цього необхiдно пiдтримувати пул або список вiльних вузлiв, який називається списком вiльного простору. Пiд час операцiї вставлення вiльний вузол видаляється iз списку вiльного простору i розмiщується у призначений лiнiйний список. I, навпаки, видалений вузол повертається до списку вiльного простору i може бути використаний для наступних вставок. Така схема управлiння пам’яттю має очевиднi переваги - у даний момент використовується простiр пам’ятi, що вiдповiдає фактичному обсяговi даних.
Iснують два пiдходи до застосовування списку вiльного простору: пiдтримка списку вiльного простору засобами мови програмування i програмна пiдтримка (застосування пiдтримує власний список вiльної пам’ятi).
Стек є найпростішим видом зв’язаного списку.
Індивідуальне завдання
Реалізувати стек за допомогою массива з фіксованою кількістю елементів та у вигляді повністю динамічної стуктури данних.
1) стек на основі масива
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define number 10
void push (char *,char **);
void pop (char *,char **);
void main (void)
{
clrscr();
char mas[number];
char * top;
top=mas;
while (1)
{
int answer;
printf("\n You want to enter the element to the stack - 1\n You want to put out the element - 2\n You want to exit - 0\n");
scanf("%d",&answer);
switch (answer)
{
case 1:
push(mas,&to...
